package 滑动;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _2841几乎唯一子数组的最大和 {
    /**
     * 
     * @param nums
     * @param m 个互不相通的元素
     * @param k 长度。固定窗口
     * @return 最大和
     */
    public static long maxSum(List<Integer> nums, int m, int k) {
        long res=0;
        long sum=0;
        Map<Integer,Integer> map= new HashMap<>();
        for (int i = 0; i < nums.size(); i++) {
            sum += nums.get(i);
            if(map.containsKey(nums.get(i))){
                int cur =map.get(nums.get(i));
                map.put(nums.get(i), cur+1);
            }else{
                map.put(nums.get(i), 1);
            }
            if(i<k-1){
                continue;
            }
            if(map.keySet().size()>=m){
                res = Math.max(res,sum);
            }
            sum -= nums.get(i-k+1);
            int start = nums.get(i-k+1);
            Integer val = map.get(start);
            if(val>1){
                map.put(start,val-1);
            }else{
                map.remove(start);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println("=========="+maxSum(Arrays.asList(2,6,7,3,1,7), 3, 4));
        System.out.println("=========="+maxSum(Arrays.asList(5,9,9,2,4,5,4), 1, 3));
        System.out.println("=========="+maxSum(Arrays.asList(1,2,1,2,1,2,1), 3, 3));
    }

}
